//#include "stdafx.h"
#include <iostream>
using namespace std;
const int N = 5;///进程数目
const int M = 3;///资源类型数目
int AllResource[M] = { 10,5,7 }; ///各类类型资源矩阵
int Available[M];///可用的资源向量
int Request[M];///请求资源向量
int Max[N][N] =
{
	///最大需求矩阵
	{7,5,3},
	{3,2,2},
	{9,0,2},
	{2,2,2},
	{4,3,3}
};
int Allocation[N][M] =
{
	///已分配资源矩阵
	{0,1,0},
	{2,0,0},
	{3,0,2},
	{2,1,1},
	{0,0,2}
};
int Need[N][N];///需求矩阵
///展示当前所有资源情况
void show()
{
	int i;
	cout << "--------------------------------------------------\n";
	cout << "当前各进程需要资源[Need]数量为：\n";
	for (i = 0; i < M; i++)
	{
		cout << "\t" << "资源" << i;
	}
	cout << endl;
	for (i = 0; i < N; i++)
	{
		cout << "进程 P" << i << ":";
		for (int j = 0; j < M; j++)
		{
			cout << "\t" << Need[i][j];
		}
		cout << endl;
	}
	cout << "\n 当前各进程已分配资源[Allocation]数量为：\n";
	for (i = 0; i < M; i++)
	{
		cout << "\t" << "资源" << i;
	}
	cout << endl;
	for (i = 0; i < N; i++)
	{
		cout << "进程 P" << i << ":";
		for (int j = 0; j < M; j++)
		{
			cout << "\t" << Allocation[i][j];
		}
		cout << endl;
	}
	cout << "\n 当前各类型资源的可利用[Available]数量为：\n";
	cout << "[";
	for (i = 0; i < M; i++)
	{
		cout << Available[i];
		if (i != M - 1) cout << ",";
	}
	cout << "]\n--------------------------------------------------\n";
}
///检验进程号是否合法
bool checkProcessId(int id)
{
	if (id < 0 || id >= N) return false;
	return true;
}
///请求资源非法对应的输出提示
void invalidRequestPrint(int id)
{
	cout << "进程 P" << id << "请求资源数目不合理，请重新输入\n";
}
///资源更新
void update(int id)
{
	for (int i = 0; i < M; i++)
	{
		Available[i] -= Request[i];
		Allocation[id][i] += Request[i];
		Need[id][i] -= Request[i];
	}
}
///恢复资源更新
void rupdate(int id)
{
	for (int i = 0; i < M; i++)
	{
		Available[i] += Request[i];
		Allocation[id][i] -= Request[i];
		Need[id][i] += Request[i];
	}
}
///安全性算法
bool safeCheck(int id)
{
	int Work[M];
	bool Finish[N];///Finish[i]=true 表示进程号为 i 的请求安全
	int safeSequence[N];///存储安全序列
	int len = 0;///记录安全序列的长度
	for (int i = 0; i < N; i++)
	{
		Finish[i] = false;
	}
	for (int j = 0; j < M; j++)
	{
		Work[j] = Available[j];
		while (checkProcessId(id))///进程号合法
		{
			if (!Finish[id] && Need[id][j] <= Work[j])
			{
				Work[j] += Allocation[id][j];
				Finish[id] = true;
				safeSequence[len++] = id;
				id = 0;
			}
			else id++;
		}
		for (int i = 0; i < N; i++)
		{
			if (!Finish[i])
			{
				cout << "\n 请求资源失败！！！\n\n";
				return false;
			}
		}
	}
	cout << "\n 请求资源成功！安全序列为：";
	for (int i = 0; i < len; i++)
	{
		cout << "P" << safeSequence[i];
		if (i != len - 1) cout << "->";
	}
	cout << "\n\n";
	return true;
}
void banker()
{
	char flag = 'y';
	while (flag == 'y' || flag == 'Y')
	{
		int i = -1;
		while (!checkProcessId(i))///进程号非法
		{
			cout << "请输入合法的请求资源的进程号，否则再次输入:P";
			cin >> i;
			if (!checkProcessId(i))
			{
				cout << "非法输入，请重新输入" << endl;
			}
		}
		for (int j = 0; j < M; j++)
		{
			cout << "进程 P" << i << "请求资源类型" << j << "的个数为:";
			cin >> Request[j];
			if (Request[j] > Need[i][j])///请求资源大于进程所需资源
			{
				invalidRequestPrint(i);
				flag = 'n';
				break;
			}
			else
			{
				///请求资源数目合理
				if (Request[j] > Available[j])///可利用的资源不够用
				{
					///请求的该资源类型的数目大于其可用资源数目
					invalidRequestPrint(i);
					flag = 'n';
					break;
				}
			}
		}
		if (flag == 'y' || flag == 'Y')
		{
			update(i);///资源更新
			if (!safeCheck(i))
			{
				///安全性算法,处于非安全状态
				rupdate(i);///恢复资源更新以便输出
			}
			else
			{
				///确认分配请求资源后能否释放资源（即收回全部分配的资源）
				bool flag = 1;
				for (int j = 0; j < M; j++)
				{
					if (Need[i][j] != 0)
					{
						flag = 0;
						break;
					}
				}
				if (flag)
				{
					for (int j = 0; j < M; j++)
						Available[j] += Allocation[i][j];
				}
			}
		}
		show();
		cout << "按'y'或'Y'继续请求资源分配，否则退出：";
		cin >> flag;
	}
}
///系统资源的初始化
void init()
{
	///初始化可利用资源向量
	int tmp;
	for (int j = 0; j < M; j++)
	{
		tmp = AllResource[j];
		for (int i = 0; i < N; i++)
		{
			tmp -= Allocation[i][j];
			if (tmp > 0)
				Available[j] = tmp;
			else
				Available[j] = 0;
		}
	}
	///初始化需求矩阵
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < M; j++)
		{
			Need[i][j] = Max[i][j] - Allocation[i][j];
		}
	}
}
int main()
{
	init();
	show();
	banker();
	return 0;
}